//给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。 
//
// 重复出现的子串要计算它们出现的次数。 
//
// 
//
// 示例 1 : 
//
// 
//输入: "00110011"
//输出: 6
//解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
//
//请注意，一些重复出现的子串要计算它们出现的次数。
//
//另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
// 
//
// 示例 2 : 
//
// 
//输入: "10101"
//输出: 4
//解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
// 
//
// 
//
// 提示： 
//
// 
// s.length 在1到50,000之间。 
// s 只包含“0”或“1”字符。 
// 
// Related Topics 双指针 字符串 
// 👍 408 👎 0

package com.cute.leetcode.editor.cn;
public class CountBinarySubstrings {
    public static void main(String[] args) {
        Solution solution = new CountBinarySubstrings().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 统计包含连续且相等长度0和1的字符串的个数
     * 有几点规律：
     *  1.子串长度一定是偶数
     *  2.连续0或者1的数目一定是字串长度的一半
     *  能不能使用长度进行遍历呢？
     *  每次遍历小区间，又将两个小区间分成了两半，同时遍历两个小区间，不相等就说明不行
     *  我这种方法不是不能做，就是超时了md
     *
     *
     *  一些c++的题解我是没看明白
     *  官方的题解：
     *      统计原始字符串中各个连续部分的长度，这样两个相邻区间的贡献就是两部分长度的最小值了
     *      比如00110011
     *      长度表为2，2，2，2 最终结果为 min(2,2)+min(2,2)+min(2,2) = 6
     */
    public int MyCountBinarySubstrings(String s) {
        int res = 0;
        int maxLen = s.length()%2==0 ? s.length(): s.length()-1;
        for (int j = 2; j <=maxLen ; j+=2) {
            for (int i = 0; i < s.length() - j + 1; i++) {
                boolean flag = true;
                int left = i;
                int right = i + j/2;
                int leftArea = s.charAt(left);
                int rightArea = s.charAt(right);
                flag = leftArea!=rightArea;
                while (left != i+j/2 && flag){
                    if (s.charAt(left)==s.charAt(right)||s.charAt(i)!=leftArea||s.charAt(right)!=rightArea){
                        flag = false;
                        break;
                    }
                    left++;right++;
                }
                if (flag) res++;
            }
        }
        return res;
    }

    /**
     * 官方题解的思路，计算当前段的最大相同长度，之后与前一段最大长度比较取小值加到结果就行了
     */
    public int countBinarySubstrings(String s) {
        int ans = 0;
        int index = 0;
        int len = s.length();
        int count = 1;//当前段的最大连续长度
        int pre = 0;//前一段的最大连续长度
        while (index<len){
            while (index < len-1 && s.charAt(index) == s.charAt(index+1)){
                count++;
                index++;
            }
            ans += Math.min(count, pre);
            pre = count;
            count = 1;//不连续之后恢复初值
            index++;
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}